package com.sort;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 快速排序，递归写法
 *               1.找一个基准数，一趟遍历下来，使得左边的数组小于基准数，右边的数字大于基准数（基准数可以随便取，一般取左边第一个数字）
 *               2.递归调用，基准数左边和右边的数据
 * @date 2022/9/18 15:31
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] nums=new int[]{2,1};

        quickSort(nums);
        for (int num : nums) {
            System.out.println(num);
        }


    }

    private static void quickSort(int[] nums) {
        //长度小于1,直接返回
        if(nums.length<=1){
            return;
        }
        //长度大于1
         sort(nums,0,nums.length-1);

    }

    private static void sort(int[] nums, int left, int right) {

        if(left>=right){
            return;
        }
        int mid=nums[left];
        int start=left;
        while (left<right){
            while (mid <nums[right]&&left<right) {
                right--;
            }
                int temp=nums[left];
                nums[left]=nums[right];
                nums[right]=temp;
            while (mid >=nums[left]&&left<right) {
                left++;
            }
                int temp1=nums[right];
                nums[right]=nums[left];
                nums[left]=temp1;
        }
        nums[left]=mid;
        sort(nums,start,left-1);
        sort(nums,left+1,nums.length-1);
    }
}
